#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: labyrinth.py 
@version:
@time: 2024/01/26

从边界入手，对边界上的可达节点进行深度优先搜索，变成了从外向内搜索

对边界上可达节点可以访问到的玩家位置做标记，那么最终只要统计出未被标记的节点个数，即为不能到达边界的玩家数量。
"""


class Player:
    directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]

    def num(self, array):
        m = len(array)
        n = len(array[0])
        res = 0
        # 在主调用函数中实现对边界节点的遍历，对边界上每一个值为1的可达节点进行深度优先搜索树，并且将已经访问过的节点位置设置为0.
        # 由于值为0的节点不会被遍历，因此可以提高效率
        # 这里理解的由外向内，就是直线的向矩阵中心遍历，所以变动的就是一个方向的坐标
        for i in range(0, n):
            if array[0][i] == 1:
                array[0][i] = 0
                self.dfs(0, i, array, m, n)
            if array[m - 1][i] == 1:
                array[m - 1][i] = 0
                self.dfs(m - 1, i, array, m, n)
        #        # 为什么是从1到m-2
        """
        x  x x x <- array[0][i]
        -  - - - 
        x| x x x|
        x| x x x|
        x  x x x <- array[m-1][i]
        -  - - - 
        
        因为上层循环已经将这两个遍历了，竖着的才是我们要访问的
        
        """
        for j in range(1, m - 2):
            if array[j][0] == 1:
                array[j][0] = 0
                self.dfs(j, 0, array, m, n)
            if array[j][n - 1] == 1:
                array[j][n - 1] = 0
                self.dfs(j, n - 1, array, m, n)
        for arr in array:
            res += arr.count(1)
        return res

    def dfs(self, i, j, array, m, n):
        for k in self.directions:
            x0 = i + k[0]
            y0 = j + k[1]
            if 0 <= x0 < m and 0 <= y0 < n and array[x0][y0] == 1:
                # 向内深度搜索如果等于1，那么赋值为0
                array[x0][y0] = 0
                self.dfs(x0, y0, array, m, n)


labyrinth1 = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
]
labyrinth2 = [
    [0, 0, 0, 0],
    [1, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
]
print(Player().num(labyrinth1))
print(Player().num(labyrinth2))
